void InsertSort(vector<int> &arr1, int length)
{
	//插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
	//插入排序在实现上，通常采用in - place排序（即只需用到O(1)的额外空间的排序），因而在小规模数据上表现良好。

	SimplePrint(arr1, length, "原始数据：");


	//有点晦涩
	//开始时有序表中只包含1个元素，序表中包含有n - 1个元素，排序过程中每次从无序序表中取出第1个元素，将它插到有序表中的适当位置，使之成为新的有序表，重复n - 1次可完成排序过程。
	//大致效果图就是左边数据有序，右边数据无序。有序的数据逐渐增加
	
	for (int i = 1; i < length; i++)  //注意初始值是1，因为要分成左右两侧.结束值是length
	{
		int start = arr1[i];
		int j = i - 1;

		while (j>=0 && arr1[j] > start)  //关键操作
		{
			//左侧的比右侧大，这此时需要把值插入到左侧位置
			arr1[j + 1] = arr1[j];
			j = j - 1;
			
		}
		arr1[j + 1] = start;
	}

	SimplePrint(arr1, length, "排序后的数据：");
	return;
}



int main()
{

	vector<int> arr = {32,4,-2,45,6,10,32,100,10};
	//简单排序，双循环遍历
	//SimpleSort(arr,arr.size());
	//BublingSort(arr, arr.size());
	InsertSort(arr, arr.size());
	//QuickSort();
	return 0;
}